#include "local_search_neighborhood_randomly.hh"
#include "construct_greedy_randomized_solution.hh"
#include "utilis.hh"

list<int> * GetNeighborsOptionalsNotMarked(Graph * G, int node, int * marked) {

	list<int> * neighbors = new list<int>();

	if(G->actived_node[node]) {
		for(int i=0; i<G->sizeG; i++)
			if(GetMatrix(G->E, node, i) && G->actived_node[i] && !marked[i] && !G->IsTerminal(i)) {
				neighbors->push_front(i);
				marked[i] = 1;
			}
	}

	return neighbors;
}


list<int> * GetNodesOfComponentRelated(Graph * G, int node) {
	list<int> * nodes = new list<int>();
	int * marked = new int[G->sizeG];
	list<int> * processed = new list<int>();
	list<int> * neighbors;
	int v;

	for(int i=0; i<G->sizeG; i++)
		marked[i] = 0;

	processed->push_front(node);
	marked[node] = 1;

	while(!processed->empty()) {

		v = processed->front();
		processed->pop_front();
		nodes->push_front(v);

		neighbors = GetNeighborsOptionalsNotMarked(G, v, marked);
		for (list<int>::iterator it=neighbors->begin(); it != neighbors->end(); ++it) {
			processed->push_back(*it);
		}
		DeleteListInt(neighbors);
	}

	DeleteListInt(processed);
	delete[] marked;
	return nodes;
}

int UpdateNodeP(Graph * G, PathMatrix * P, int node) {

	list<Path*>::iterator it;

	for(int i=0; i<P->sizeP; i++) {
		for(int j=i; j<P->sizeP; j++) {

			it = P->P[i][j]->begin();
			while(it != P->P[i][j]->end()) {
				if((*it)->Contains(node)) {
					delete (*it);
					it = P->P[i][j]->erase(it);
					G->R[i][j]++;
				}
				else
					it++;
			}
		}
	}
	return 0;
}

pair<Graph*, PathMatrix*> * RemoveOptionalNodesFromRelatedComponentOfOptionals(Graph * G, PathMatrix * P, double alfa) {

	PathMatrix * P_part = new PathMatrix(P);
	Graph * G_part = new Graph(G);
	list<int> * optinal_nodes = new list<int>();
	list<int> * component_nodes;
	int cant_optional_nodes_to_quit;
	int nodes_out;
	int node;


	// Tomo todos los nodos opcionales pertenecientes a la solucion
	for(int i=0; i<G->sizeG; i++)
		if(G->actived_node[i] && !G->IsTerminal(i)) optinal_nodes->push_front(i);

	cant_optional_nodes_to_quit = Random(((int)(optinal_nodes->size() * alfa)) + 1);

	if(!optinal_nodes->empty()) {
		nodes_out = 0;
		while(nodes_out < cant_optional_nodes_to_quit && !optinal_nodes->empty()) {
			node = SelectRandom(optinal_nodes); // selecciona uno y lo remueve de la lista
			component_nodes = GetNodesOfComponentRelated(G_part, node);

			while(nodes_out < cant_optional_nodes_to_quit && !component_nodes->empty()) {
				node = SelectRandom(component_nodes); // selecciona uno y lo remueve de la lista

				//cout << "Remove:  " << node+1 << endl;
				G_part->actived_node[node] = 0;
				UpdateNodeP(G_part, P_part, node);

				nodes_out++;
			}
			DeleteListInt(component_nodes);
		}
	}

	DeleteListInt(optinal_nodes);

	return new pair<Graph*, PathMatrix*>(G_part, P_part);
}


list< pair<Graph*, PathMatrix*> * > * NeighborhoodByEliminatingEdges(Graph * G_problem, Graph * G_sol, PathMatrix * P_sol, int k, double beta, int max_iter)
{
	list< pair<Graph*, PathMatrix*> * > * neighbors = new list< pair<Graph*, PathMatrix*> * >();
	pair<Graph*, PathMatrix*> * G_P_part, * G_P_aster;

	for(int i=0; i<max_iter; i++) {

		G_P_part = RemoveEdgesFromRelatedComponentOfTerminals(G_sol, P_sol, beta);
		G_P_aster = Construct(G_problem, G_P_part->first, G_P_part->second, k);

		if (G_P_aster) {
			neighbors->push_front(G_P_aster);
		}

		DeletePair(G_P_part);
	}

	return neighbors;
};

list<int> * GetNeighborsTerminalsNotMarked(Graph * G, int node, int * marked) {
	list<int> * neighbors = new list<int>();

	if(G->actived_node[node]) {
		for(int i=0; i<G->sizeG; i++)
			if(GetMatrix(G->E, node, i) && G->actived_node[i] && !marked[i] && G->IsTerminal(i)) {
				neighbors->push_front(i);
				marked[i] = 1;
			}
	}

	return neighbors;
}

list<pair<int,int> * > * GetEdgesOfComponentRelated(Graph * G, int node) {

	list<int>::iterator it0;
	list<pair<int,int> * > * edges = new list<pair<int,int> * >();
	list<int> * nodes = new list<int>();
	int * marked = new int[G->sizeG];
	list<int> * processed = new list<int>();
	list<int> * neighbors = new list<int>();
	int v;

	for(int i=0; i<G->sizeG; i++)
		marked[i] = 0;

	processed->push_front(node);
	marked[node] = 1;

	while(!processed->empty()) {

		v = processed->front();
		processed->pop_front();
		nodes->push_front(v);

		neighbors = GetNeighborsTerminalsNotMarked(G, v, marked);
		for (list<int>::iterator it=neighbors->begin(); it != neighbors->end(); ++it) {
			processed->push_back(*it);
		}
		DeleteListInt(neighbors);
	}

	// Grafo inducido de "nodes"
	it0 = nodes->begin();
	while(it0 != nodes->end()) {
		v = *it0;
		it0 = nodes->erase(it0);
		for (list<int>::iterator it1=nodes->begin(); it1 != nodes->end(); ++it1) {
			if(GetMatrix(G->E, v, *it1)) edges->push_front(new pair<int, int>(v, *it1));
		}
	}


	DeleteListInt(nodes);
	DeleteListInt(processed);
	delete[] marked;
	return edges;
}


int UpdateEdgeP(Graph * G, PathMatrix * P, pair<int,int> * edge) {

	list<Path*>::iterator it;

	for(int i=0; i<P->sizeP; i++) {
		for(int j=i; j<P->sizeP; j++) {

			it = P->P[i][j]->begin();
			while(it != P->P[i][j]->end()) {
				if((*it)->Contains(edge)) {
					delete (*it);
					it = P->P[i][j]->erase(it);
					G->R[i][j]++;
				}
				else
					it++;
			}
		}
	}
	return 0;
}

pair<Graph*, PathMatrix*> * RemoveEdgesFromRelatedComponentOfTerminals(Graph * G, PathMatrix * P, double beta) {

	PathMatrix * P_part = new PathMatrix(P);
	Graph * G_part = new Graph(G);
	list<int> * terminals_nodes = new list<int>();
	list<pair<int,int> * > * component_edges;
	int cant_terminals_to_quit;
	int edges_out;
	pair<int,int> * edge;
	int node;

	// Tomo todos los nodos opcionales pertenecientes a la solucion
	for(int i=0; i<G->sizeG; i++)
		if(G->actived_node[i] && G->IsTerminal(i)) terminals_nodes->push_front(i);

	cant_terminals_to_quit = Random(((int)(terminals_nodes->size() * beta)) + 1);

	//cout << "Terminals Node    "<< endl;
	//PrintListInt(terminals_nodes);

	if(!terminals_nodes->empty()) {
		edges_out = 0;
		while(edges_out < cant_terminals_to_quit && !terminals_nodes->empty()) {
			node = SelectRandom(terminals_nodes); // selecciona uno y lo remueve de la lista

			//cout << "Node    " << node+1 << endl;
			component_edges = GetEdgesOfComponentRelated(G_part, node);

			while(edges_out < cant_terminals_to_quit && !component_edges->empty()) {
				edge = SelectRandom(component_edges); // selecciona uno y lo remueve de la lista

				//cout << "Remove:    ("<< edge->first+1 << ", "<< edge->second+1 << ")" << endl;
				SetMatrix(G_part->E, edge->first, edge->second , 0);
				UpdateEdgeP(G_part, P_part, edge);
				delete edge;
				edges_out++;
			}
			DeleteListPairInt(component_edges);
		}
	}

	DeleteListInt(terminals_nodes);

	return new pair<Graph*, PathMatrix*>(G_part, P_part);
}


list< pair<Graph*, PathMatrix*> * > * NeighborhoodByEliminatingNodes(Graph * G_problem, Graph * G_sol, PathMatrix * P_sol, int k, double alfa, int max_iter)
{
	list< pair<Graph*, PathMatrix*> * > * neighbors = new list< pair<Graph*, PathMatrix*> * >();
	pair<Graph*, PathMatrix*> * G_P_part, * G_P_aster;

	for(int i=0; i<max_iter; i++) {

		G_P_part = RemoveOptionalNodesFromRelatedComponentOfOptionals(G_sol, P_sol, alfa);
		G_P_aster = Construct(G_problem, G_P_part->first, G_P_part->second, k);

		if (G_P_aster) {
			neighbors->push_front(G_P_aster);
		}
		DeletePair(G_P_part);

	}
	return neighbors;
};
